#include<bits/stdc++.h>

// 在线求lca模版，初始化参数 节点数量（编号1 - n），根节点，图（vector套vector形式）
struct LCA{
    int n, s, cnt;
    vector<vector<int>> e; 
    vector<int> dep, sz, son, top, f, in;
    LCA(int n_, int s_, vector<vector<int>> &e_) {
        n = n_, s = s_;
        e = e_;
        cnt = 0;
        dep.assign(n + 1, 0), sz.assign(n + 1, 0), son.assign(n + 1, 0), top.assign(n + 1, 0), f.assign(n + 1, 0);
        in.assign(n + 1, 0);
        dfs1(s, 0); dfs(s, s, s);
    }
    void dfs1(int u, int fa) {
        in[u] = ++cnt;
        dep[u] = dep[fa] + 1, sz[u] = 1, f[u] = fa;
        for(int v : e[u]) {
            if(v == fa) continue;
            dfs1(v, u);
            sz[u] += sz[v];
            if(son[u] == 0 || sz[v] > sz[son[u]]) {
                son[u] = v;
            }
        }
    }
    void dfs(int u, int fa, int topu) {
        top[u] = topu;
        if(son[u] == 0) return;
        dfs(son[u], u, topu);
        for(int v : e[u]) {
            if(v == fa || v == son[u]) continue;
            dfs(v, u, v);
        }
    }
    int lca(int u, int v) {
        while(1) {
            if(top[u] == top[v]) return dep[u] <= dep[v] ? u : v;
            if(dep[top[u]] < dep[top[v]]) swap(u, v);
            u = f[top[u]];
        }
        return 0;
    }
};


// dfs序 RMQ O(1)lca  1 编号开始
struct Lca {
    vector<vector<int>>& e;
    vector<int> dep, in;
    vector<vector<int>> st;
    int s, n, m, dfn;
    Lca(int n_, vector<vector<int>>& e_, int s_) : n(n_), s(s_), e(e_){
        m = __lg(n), dfn = 0;
        dep.assign(n + 1, 0); in = dep;
        st.assign(m + 1, vector<int> (n + 1, 0));
        function<void(int, int)> pdfs = [&] (int u, int fa) {
            in[u] = ++dfn;
            st[0][dfn] = fa;
            for(auto v : e[u]) {
                if(v == fa) continue;
                dep[v] = dep[u] + 1;
                pdfs(v, u);
            }
        };
        pdfs(s, s);
        for(int j = 1; j <= m; j++) for(int i = 1; i <= n; i++) {
            if(i + (1 << j - 1) > n) break;
            int x = st[j - 1][i], y = st[j - 1][i + (1 << j - 1)];
            st[j][i] = dep[x] < dep[y] ? x : y;
        }
    }
    int lca(int u, int v) {
        if(u == v) return u;
        if(in[u] > in[v]) swap(u, v);
        int x = in[u] + 1, y = in[v];
        int j = x == y ? 0 : __lg(y - x + 1);
        x = st[j][x], y = st[j][y - (1 << j) + 1];
        return dep[x] < dep[y] ? x : y;
    }
    int dis(int u, int v) {
        int l = lca(u, v);
        return dep[u] + dep[v] - dep[l] * 2;
    }
};


// 建虚树模版，需要用到lca模版初始化
struct Vir_Tree {
    LCA &Lca;
    vector<vector<int>> E;
    Vir_Tree(LCA &Lca_) : Lca(Lca_) {
        E.assign(Lca_.n + 1, vector<int>());
    }
    // 传入关键点（包含根节点1） 注意！！dfs时清空E数组方便下次建树！！
    void build(vector<int> &a) {
        sort(a.begin(), a.end(), [&](int x, int y) {return Lca.in[x] < Lca.in[y];});
        int n = a.size();
        for(int i = 0;i < n - 1;i ++) {
            int lc = Lca.lca(a[i], a[i + 1]);
            a.push_back(lc);
        }
        sort(a.begin(), a.end(), [&](int x, int y) {return Lca.in[x] < Lca.in[y];});
        a.erase(unique(a.begin(), a.end()) , a.end());

        n = a.size();        
        for(int i = 0;i < n - 1;i ++) {
            int lc = Lca.lca(a[i], a[i + 1]);
            E[lc].push_back(a[i + 1]);
        }
    }
};

const int inf = 1e9;
struct Flow {
	struct nd {
		int v;
		ll w;
		int ne;
	};
	vector<nd> e;
	vector<int> head, dep, now;
	int n;
	Flow (int n_) {
		n = n_ + 10;
		head.resize(n), dep.resize(n), now.resize(n);
		e.resize(2);
	}
	void add1 (int u, int v, ll w) {
		e.push_back({v, w, head[u]}); head[u] = e.size() - 1;
	}
	void add(int u, int v, ll w) {
		add1(u, v, w), add1(v, u, 0);
	}
	
	bool bfs(int s, int t) {
		fill(dep.begin(), dep.end(), inf);
		dep[s] = 0, now[s] = head[s];
		queue<int> q;
		q.push(s);
		while(q.size()) {
			int u = q.front(); q.pop();
			if(u == t) return true;
			for(int i = head[u]; i; i = e[i].ne) {
				int v = e[i].v; ll w = e[i].w;
				if(dep[v] != inf || w == 0) continue;
				dep[v] = dep[u] + 1;
				now[v] = head[v];
				q.push(v);
			}
		}	
		return false;
	}
	
	ll dfs (int u, int t, ll sum) {
		if(u == t) return sum;
		ll res = 0;
		for(int i = now[u]; i && sum; i = e[i].ne) {
			now[u] = i;
			int v = e[i].v; ll w = e[i].w;
			if(w == 0 || dep[v] != dep[u] + 1) continue;
			ll f = dfs(v, t, min(sum, w));
			
			e[i].w -= f, e[i ^ 1].w += f, sum -= f, res += f;
		}
		return res;
	}
    int s;
	ll wk (int s, int t) {
        this->s = s;
		ll f = 0;
		while(bfs(s, t)) {
			f += dfs(s, t, 1e18);
		}
		return f;
	}
    vector<vector<pair<int, ll>>> show() {
        vector E(n + 1, vector<pair<int, ll>>());
        for (int u = 0; u <= n; u++) {
            for (int i = head[u]; i; i = e[i].ne) {
                auto [v, w, ne] = e[i];
                E[u].push_back({v, w});
            }
        }
        return E;
    }
    vector<pii> minCut() {
        queue<int> q;
        q.push(s);
        vector<int> visi(n + 1);
        visi[s] = 1;
        while (q.size()) {  
            auto u = q.front(); q.pop();
            for (int i = head[u]; i; i = e[i].ne) {
                auto [v, w, _] = e[i];
                if (visi[v] || w == 0) continue;
                visi[v] = 1;
                q.push(v);
            }
        }
        vector<pii> ans;
        for (int u = 0; u <= n; u++) {
            for (int i = head[u]; i; i = e[i].ne) {
                auto [v, w, _] = e[i];
                if (visi[u] ^ visi[v]) {
                    ans.push_back({u, v});
                }
            }
        }
        return ans;
    }
};

template<class T>
struct MCMF {
    struct edge {
        int v; T c, w; int ne;
    };
    int n;
    vector<edge> e;
    vector<int> head, pre;
    vector<bool> visi;
    vector<T> d, mf;
    MCMF(int n_) : n(n_) {
        int N = n + 10; e.resize(2);
        head.resize(N), d.resize(N), mf.resize(N), pre.resize(N), visi.resize(N);
    }
    void add_edge(int u, int v, T c, T w) {
        e.push_back({v, c, w, head[u]}); head[u] = e.size() - 1;
    }
    void add(int u, int v, T c, T w) {
        add_edge(u, v, c, w); add_edge(v, u, 0, -w);
    }
    bool spfa(int s, int t) {
        fill(d.begin(), d.end(), numeric_limits<T>::max());
        fill(mf.begin(), mf.end(), 0);
        queue<int> q; q.push(s);
        d[s] = 0, mf[s] = numeric_limits<T>::max(), visi[s] = 1;
        while(q.size()) {
            int u = q.front(); q.pop(); visi[u] = 0;
            for(int i = head[u]; i; i = e[i].ne) {
                auto [v, c, w, _] = e[i];
                if(d[v] > d[u] + w && c) {
                    d[v] = d[u] + w, mf[v] = min(mf[u], c);
                    pre[v] = i;
                    if(!visi[v]) q.push(v), visi[v] = 1;
                }
            }
        }
        return mf[t] > 0;
    }
    array<T, 2> wk(int s, int t) {
        T flow = 0, cost = 0;
        while(spfa(s, t)) {
            for(int v = t; v != s; ) {
                int i = pre[v]; 
                e[i].c -= mf[t]; e[i ^ 1].c += mf[t];
                v = e[i ^ 1].v;
            }
            flow += mf[t], cost += mf[t] * d[t];
        }
        return {flow, cost};
    }
};

// 有向图点双
struct SCC {
    int n, cnt, dfn;
    stack<int> st;
    vector<int> low, num, res;
    vector<vector<int>> e;
    SCC() {

    }
    SCC(int n_) {
        n = n_, dfn = 0, cnt = 0;
        low.assign(n + 1, 0);
        num.assign(n + 1, 0);
        res.assign(n + 1, 0);
        e.assign(n + 1, vector<int>{});
    }

    void add_edge(int u, int v) {
        e[u].push_back(v);
    }

    function<void(int)> dfs = [&](int u) {
        low[u] = num[u] = ++dfn;
        st.push(u);
        for(auto v : e[u]) {
            if(!num[v]) {
                dfs(v);
                low[u] = min(low[u], low[v]);
            } else if (!res[v]) {
                low[u] = min(low[u], num[v]);
            }
        }
        if(low[u] == num[u]) {
            cnt++;
            while(1) {
                int v = st.top(); st.pop();
                res[v] = cnt;
                if(v == u) break;
            }
        }
    };
    function<vector<int>()> wk = [&]() {
        for(int i = 1; i <= n; i++) {
            if(!num[i]) {
                dfs(i);
            }
        }
        return res;
    };
};

// 边双联通分量缩点。可支持重边，传入邻接矩阵带边id的
// 下标1 - n 并且e不能开大，否则n不对
struct Edcc{
    int n, dfn = 0, cnt = 0;
    vector<int> num, low, edcc;
    stack<int> st; 
    Edcc(vector<vector<array<int, 2>>> &e) {
        int n = e.size() - 1;
        low.assign(n + 1, 0), edcc.assign(n + 1, 0), num.assign(n + 1, 0);
        function<void(int, int)> dfs = [&] (int u, int id) {
            low[u] = num[u] = ++dfn; st.push(u);
            for(auto [v, i] : e[u]) {
                if(i == id) continue;
                if(!low[v]) dfs(v, i);
                low[u] = min(low[u], low[v]);
            }
            if(low[u] == num[u]) {
                cnt++;
                while(1) {
                    int v = st.top(); st.pop();
                    edcc[v] = cnt;
                    if(v == u) break;
                }
            }
        };
        for(int u = 1; u <= n; u++) {
            if(!low[u]) dfs(u, -1);
        }
    }
};


// 树剖+线段树结合
template<class Info, class Tag>
struct Segment {
	int n;
	vector<Info> info;
	vector<Tag> tag;
	Segment(int n_, vector<Info> & init) {
		n = n_; info.resize(n * 4 + 10), tag.resize(n * 4 + 10);
		build(1, 1, n, init);
	}
    Segment(int n_) {
        n = n_;
        info.assign(n * 4 + 10, {}), tag.assign(n * 4 + 10, {});
    }
	void build(int u, int l, int r, vector<Info> &init) {
		if(l == r) {info[u] = init[l]; return;}
		int mid = l + r >> 1;
		build(u * 2, l, mid, init); build(u * 2 + 1, mid + 1, r, init);
		info[u] = info[u * 2] + info[u * 2 + 1];
	}
	Info query(int u, int l, int r, int ul, int ur) {
		if(l <= ul && r >= ur) return info[u];
		int mid = ul + ur >> 1;
		push_down(u);
		if(r <= mid) return query(u * 2, l, r, ul, mid);
		if(l > mid) return query(u * 2 + 1, l, r, mid + 1, ur);
		return query(u * 2, l, r, ul, mid) + query(u * 2 + 1, l, r, mid + 1, ur);
	}
	Info query(int l, int r) {
		return query(1, l, r, 1, n);
	}
	void push(int v,const Tag & t) {
		tag[v].aply(t); 
		info[v].aply(t);
	}
	void push_down(int u) {
		push(u * 2, tag[u]); push(u * 2 + 1, tag[u]);
		tag[u] = Tag();
	}
	void change(int u, int l, int r, const Tag& x, int ul, int ur) {
		if(l <= ul && r >= ur) {
			push(u, x);
			return;
		}
		int mid = ul + ur >> 1;
		push_down(u);
		if(l <= mid) change(u * 2, l, r, x, ul, mid);
		if(r > mid) change(u * 2 + 1, l, r, x, mid + 1, ur);
		info[u]	= info[u * 2] + info[u * 2 + 1];
	}
	void change(int l, int r, const Tag& x) {
		change(1, l, r, x, 1, n);
	}
};
struct Tag {
    void aply(const Tag& t) {
    }
};
struct Info {
    void aply(const Tag& t) {
    }
    Info operator+(const Info& t) const {
    }
};

struct HLD {
    int n, s, dfn;
    vector<vector<int>> &e;
    vector<int> sz, top, f, in, out, son, dep, bot, id;
    Segment<Info, Tag> &tr;
    HLD(int n_, int s_, vector<vector<int>> &e_, Segment<Info, Tag> &tr_) : n(n_), s(s_), e(e_), tr(tr_) {
        dfn = 0;
        sz.assign(n + 1, 0); top = f = in = dep = bot = id = out = son = sz;
        dfs1(s, s);
        dfs2(s, s, s);
    }
    void dfs1(int u, int fa) {
        sz[u] = 1;
        for (auto v : e[u]) {
            if (v == fa) continue;
            dep[v] = dep[u] + 1;
            f[v] = u;
            dfs1(v, u);
            if (sz[v] > sz[son[u]]) son[u] = v;
            sz[u] += sz[v];
        }
    }
    void dfs2(int u, int fa, int t) {
        top[u] = t;
        in[u] = ++dfn;
        id[dfn] = u;
        if (son[u]) dfs2(son[u], u, t);
        for (auto v : e[u]) {
            if (v == son[u] || v == fa) continue;
            dfs2(v, u, v);
        }
        bot[u] = son[u] ? bot[son[u]] : u;
        out[u] = dfn; 
    }
    int lca(int u, int v) {
        while (top[u] ^ top[v]) {
            if (dep[top[u]] < dep[top[v]]) swap(u, v);
            u = f[top[u]];
        }
        return dep[u] < dep[v] ? u : v;
    }
    Info queryTree(int u) {
        return tr.query(in[u], out[u]);
    }
    void changeTree(int u, const Tag& t) {
        tr.change(in[u], out[u], t);
    }
    void changeChain(int u, int v, const Tag& t) {
        while (top[u] ^ top[v]) {
            if (dep[top[u]] < dep[top[v]]) swap(u, v);
            tr.change(in[top[u]], in[u], {t});
            u = f[top[u]];
        }
        int l = in[u], r = in[v];
        if (l > r) swap(l, r);
        tr.change(l, r, {t});
    }
    Info queryChain(int u, int v) {
        auto res = Info();
        while (top[u] ^ top[v]) {
            if (dep[top[u]] < dep[top[v]]) swap(u, v);
            res = res + tr.query(in[top[u]], in[u]);
            u = f[top[u]];
        }
        int l = in[u], r = in[v];
        if (l > r) swap(l, r);
        res = res + tr.query(l, r);
        return res;
    }
};




/*
dinic
带上下界网络流
*/
template<class T>
struct Flow {
    const int inf = 1e9;
    struct edge {
        int v; T w; int ne; 
    };
    int n;
    vector<edge> e;
    vector<int> head, now, dep;
    
    vector<T> in; // 上下界用到
    Flow (int n_) : n(n_) {
        e.resize(2);
        int N = n + 10;
        head.resize(N), now.resize(N), dep.resize(N);
        in.resize(N);
    }
    void add_edge(int u, int v, T w) {
        e.push_back((edge){v, w, head[u]});
        head[u] = e.size() - 1;
    }
    void add(int u, int v, T w) {
        add_edge(u, v, w); add_edge(v, u, 0);
    }
    // 上下界用到
    void add(int u, int v, T l, T r) {
        in[v] += l, in[u] -= l;
        add(u, v, r - l);
    }

    bool bfs(int s, int t) {
        fill(dep.begin(), dep.end(), inf);
        dep[s] = 0, now[s] = head[s];
        queue<int> q; q.push(s);
        while(q.size()) {
            int u = q.front(); q.pop();
            for(int i = head[u]; i; i = e[i].ne) {
                int v = e[i].v;
                if(e[i].w > 0 && dep[v] == inf) {
                    q.push(v);
                    now[v] = head[v], dep[v] = dep[u] + 1;
                    if(v == t) return 1;
                }
            }
        }
        return 0;
    }
    T dfs(int u, int t, T sum) {
        if(u == t) return sum;
        T k, flow = 0;
        for(int i = now[u]; i > 0 && sum > 0; i = e[i].ne) {
            now[u] = i; int v = e[i].v;
            if(e[i].w > 0 && (dep[v] == dep[u] + 1)) {
                k = dfs(v, t, min(sum, (T)e[i].w));
                if(k == 0) dep[v] = inf;
                e[i].w -= k; e[i ^ 1].w += k, flow += k, sum -= k;
            }
        } 
        return flow;
    }
    
    T wk(int s, int t) {
        T ans = 0;
        while(bfs(s, t)) ans += dfs(s, t, numeric_limits<T>::max());
        return ans;
    }
    // 上下界用到
    T wklr(int s, int t, int ismin = 0) {
        T ans = 0, tot = 0;
        int ss = n + 1, tt = n + 2;
        for (int i = 0; i <= n; i++) {
            if (in[i] > 0) add(ss, i, in[i]), tot += in[i];
            else add(i, tt, -in[i]);
        }
        add(t, s, numeric_limits<T>::max());
        ans = wk(ss, tt);
        if (tot != ans) {
            return -1;
        }
        int cc = e.size();
        ans = e[cc - 1].w;
        e[cc - 1].w = 0, e[cc - 2].w = 0;
        return ans + (ismin ? -wk(t, s) : wk(s, t));
    }
    vector<vector<pair<int, T>>> show() {
        vector E(n + 1, vector<pair<int, T>>());
        for (int u = 0; u <= n; u++) {
            for (int i = head[u]; i; i = e[i].ne) {
                auto [v, w, ne] = e[i];
                E[u].push_back({v, w});
            }
        }
        return E;
    }
    vector<pii> minCut(int s) {
        queue<int> q;
        q.push(s);
        vector<int> visi(n + 1);
        visi[s] = 1;
        while (q.size()) {  
            auto u = q.front(); q.pop();
            for (int i = head[u]; i; i = e[i].ne) {
                auto [v, w, _] = e[i];
                if (visi[v] || w == 0) continue;
                visi[v] = 1;
                q.push(v);
            }
        }
        vector<pii> ans;
        for (int u = 0; u <= n; u++) {
            for (int i = head[u]; i; i = e[i].ne) {
                auto [v, w, _] = e[i];
                if (visi[u] ^ visi[v]) {
                    ans.push_back({u, v});
                }
            }
        }
        return ans;
    }
};



/*
上下界最小费用最大流，用得不多，不一定对
*/
template<class T>
struct MCMF {
    struct edge {
        int v; T c, w; int ne;
    };
    int n;
    vector<edge> e;
    vector<int> head, pre;
    vector<bool> visi;
    vector<T> d, mf;
    vector<T> in; T totcost;// 上下界
    MCMF(int n_) : n(n_) {
        totcost = 0;
        int N = n + 10; e.resize(2);
        head.resize(N), d.resize(N), mf.resize(N), pre.resize(N), visi.resize(N), in.resize(N);
    }
    void add_edge(int u, int v, T c, T w) {
        e.push_back({v, c, w, head[u]}); head[u] = e.size() - 1;
    }
    void add(int u, int v, T c, T w) {
        add_edge(u, v, c, w); add_edge(v, u, 0, -w);
    }
    void add(int u, int v, T l, T r, T w) {
        totcost += l * w;
        in[v] += l, in[u] -= l;
        add(u, v, r - l, w);
    }
    bool spfa(int s, int t) {
        fill(d.begin(), d.end(), numeric_limits<T>::max());
        fill(mf.begin(), mf.end(), 0);
        queue<int> q; q.push(s);
        d[s] = 0, mf[s] = numeric_limits<T>::max(), visi[s] = 1;
        while(q.size()) {
            int u = q.front(); q.pop(); visi[u] = 0;
            for(int i = head[u]; i; i = e[i].ne) {
                auto [v, c, w, _] = e[i];
                if(d[v] > d[u] + w && c) {
                    d[v] = d[u] + w, mf[v] = min(mf[u], c);
                    pre[v] = i;
                    if(!visi[v]) q.push(v), visi[v] = 1;
                }
            }
        }
        return mf[t] > 0;
    }
    array<T, 2> wk(int s, int t) {
        T flow = 0, cost = 0;
        while(spfa(s, t)) {
            for(int v = t; v != s; ) {
                int i = pre[v]; 
                e[i].c -= mf[t]; e[i ^ 1].c += mf[t];
                v = e[i ^ 1].v;
            }
            flow += mf[t], cost += mf[t] * d[t];
        }
        return {flow, cost};
    }
    /*
    有源汇上下界最小费用最大流
    */
    array<T, 2> wklr(int s, int t) {
        int ss = n + 1, tt = n + 2;
        T tot = 0;

        for (int i = 0; i <= n; i++) {
            if (in[i] > 0) add(ss, i, in[i], 0), tot += in[i];
            else if (in[i] < 0) add(i, tt, -in[i], 0);
        }
        add(t, s, numeric_limits<T>::max(), 0);
        auto res = wk(ss, tt);
        if (res[0] != tot) {
            return {-1, -1};
        }
        int cnt = e.size();
        res[0] = e[cnt - 1].c;
        e[cnt - 1].c = e[cnt - 2].c = 0;
        auto res1 = wk(s, t);
        res[0] += res1[0], res[1] += res1[1] + totcost;
        return res;
    }
};

